package acm.pta10;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 直捣黄龙 {
    public static void main(String[] args) {
        Reader sc = new Reader();
        Graph graph = new Graph();
        int n = sc.nextInt();
        int m = sc.nextInt();
        String start = sc.next();
        String end = sc.next();
        graph.addNode(new Node(start, 0));
        while (--n > 0) {
            Node node = new Node(sc.next(), sc.nextInt());
            graph.addNode(node);
        }
        while (m-- > 0) {
            graph.addEdge(sc.next(), sc.next(), sc.nextInt());
        }
        LinkedList<Node> dijkstra = dijkstra(graph, graph.map.get(start), graph.map.get(end));
        StringBuilder sb = new StringBuilder();
        for (Node node : dijkstra) {
            sb.append(node.name).append("->");
        }
        sb.delete(sb.length() - 2, sb.length());
        System.out.println(sb);
        System.out.println(dijkstra.getLast().pass + " " + dijkstra.getLast().time + " " + dijkstra.getLast().countTotal);
    }

    public static LinkedList<Node> dijkstra(Graph graph, Node s, Node e) {
        NodHeap<Node> nodHeap = new NodHeap<>(graph.map.size());
        nodHeap.setComparator((old, young) -> {
            if (old.time == young.time) {
                if (old.pass == young.pass)
                    return young.countTotal > old.countTotal;
                return young.pass > old.pass;
            }
            return young.time < old.time;
        });
        nodHeap.setUpdater((node, info) -> {
            node.time = info.time;
            node.pass = info.pass;
            node.countTotal = info.countTotal;
        });
        nodHeap.addOrUpdateOrIgnore(s, s, null);
        Node info = new Node(0, 0, 0);
        while (nodHeap.isNotEmpty()) {
            Node curr = nodHeap.pop();
            if (curr == e) break;
            for (Edge edge : curr.next) {
                Node to = edge.to;
                info.time = curr.time + edge.time;
                info.pass = curr.pass + 1;
                info.countTotal = curr.countTotal + to.count;
                nodHeap.addOrUpdateOrIgnore(to, info, curr);
            }
        }
        return nodHeap.preList(e);
    }

    static class Graph {
        Map<String, Node> map = new HashMap<>();

        public void addNode(Node o) {
            map.put(o.name, o);
        }

        public void addEdge(String from, String to, int time) {
            Node fromNode = map.get(from);
            Node toNode = map.get(to);
            Edge from_to = new Edge(fromNode, toNode, time);
            Edge to_from = new Edge(toNode, fromNode, time);
            fromNode.next.add(from_to);
            toNode.next.add(to_from);
        }
    }

    static class Node {
        String name;
        int time;
        int pass;
        int count;
        int countTotal;
        List<Edge> next = new LinkedList<>();

        public Node(String name, int count) {
            this.name = name;
            this.count = count;
            this.countTotal = count;
        }

        public Node(int time, int pass, int count) {
            this.time = time;
            this.pass = pass;
            this.count = count;
        }
    }

    static class Edge {
        Node from;
        Node to;
        int time;

        public Edge(Node from, Node to, int time) {
            this.from = from;
            this.to = to;
            this.time = time;
        }
    }

    static class NodHeap<T> {
        private Map<T, Integer> indexMap;
        private Map<T, T> preMap;
        private T[] heap;
        private int heapSize = 1;
        private MyComparator<T> comparator;
        private MyUpdater<T> updater;

        /**
         * node:原节点
         * info:走另一条路线的信息
         */
        public void addOrUpdateOrIgnore(T node, T info, T pre) {
            Integer i = indexMap.get(node);
            if (i != null) {    //堆中存在node的情况
                if (comparator.compare(node, info)) {    //是否需要更新
                    insert(node, info, pre, i);
                    sink(i);
                }
                return;
            }
            insert(node, info, pre, heapSize++);
        }

        /**
         * 更新node的索引、前缀、以及信息
         */
        public void insert(T node, T info, T pre, int i) {
            heap[i] = node;
            indexMap.put(node, i);
            preMap.put(node, pre);
            updater.update(node, info);
            rise(i);
        }

        public T pop() {
            T pop = heap[1];
            swap(1, --heapSize);
            sink(1);
            return pop;
        }

        public NodHeap(int size) {
            indexMap = new HashMap<>(size);
            preMap = new HashMap<>(size);
            this.heap = (T[]) new Object[size + 1];   //0位置弃而不用
        }

        public void swap(int a, int b) {
            T node = heap[a];
            heap[a] = heap[b];
            heap[b] = node;
            indexMap.put(heap[a], a);
            indexMap.put(heap[b], b);
        }

        /**
         * 从指定位置向上升起
         */
        public void rise(int i) {
            while (i != 1) {  //不是根节点
                int parent = i >> 1;
                if (!comparator.compare(heap[parent], heap[i])) {   //无需上升
                    break;
                }
                swap(parent, i);
                i = parent;
            }
        }

        /**
         * 从指定位置向下沉
         */
        public void sink(int i) {
            while (!isLeaf(i)) {     //并非叶子节点
                int child = topChild(i);
                if (!comparator.compare(heap[i], heap[child])) {   //当前节点是最小的，无需下沉
                    break;
                }
                swap(i, child);
                i = child;
            }
        }

        public int topChild(int i) {
            int l = i << 1;
            int r = i << 1 | 1;
            if (r >= heapSize) {
                return l;
            }
            if (comparator.compare(heap[l], heap[r])) {
                return r;
            }
            return l;
        }

        public boolean isLeaf(int i) {
            return i << 1 >= heapSize;
        }

        public LinkedList<T> preList(T o) {
            LinkedList<T> list = new LinkedList<>();
            while (o != null) {
                list.addFirst(o);
                o = preMap.get(o);
            }
            return list;
        }

        public boolean isNotEmpty() {
            return heapSize > 1;
        }

        public static void main(String[] args) {
            NodHeap<Integer> nodHeap = new NodHeap<Integer>(3);
            nodHeap.setComparator(((old, young) ->young > old));
            System.out.println();
        }

        public void setUpdater(MyUpdater<T> updater) {
            this.updater = updater;
        }

        public void setComparator(MyComparator<T> comparator) {
            this.comparator = comparator;
        }

        public interface MyComparator<T> {
            /**
             * 返回true需要更新，false无需更行
             *
             * @param old
             * @param young
             * @return
             */
            boolean compare(T old, T young);
        }

        public interface MyUpdater<T> {
            void update(T old, T young);
        }
    }

    static class Reader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {    //内存中没有
                String nextLine = innerNextLine();
                if (nextLine == null) {     //且没有下一行
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);  //读入一行
            }
            return true;
        }

        public String nextLine() {
            tokenizer = new StringTokenizer("");    //清空内存中的字符
            return innerNextLine();
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}
